package intersect;

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        ArrayList<Integer> list = new ArrayList<>();
        while(i<nums1.length&&j<nums2.length){
            if(nums1[i] == nums2[j]){
             // 统计有好多个
                int num1 = getCount(nums1,nums1[i],i);
                int num2 = getCount(nums2,nums2[j],j);
                int count = Math.min(num1,num2);
                for (int k = 0; k < count; k++) {
                    list.add(nums1[i]);
                }
                i+=num1;
                j+=num2;
            }else if(nums1[i]<nums2[j]){
                i++;
            }else{
                j++;
            }
        }
        // 1 1 2 3 5 9 9
        // 1 1 3 3 6 9
        int[] arr = new int[list.size()];
        for (int k = 0; k < list.size(); k++) {
            arr[k] = list.get(k);
        }
        return arr;
    }
    private int getCount(int[]nums,int target,int startIndex){
        int res = 0;
        for (int i = startIndex; i < nums.length; i++) {
            if(nums[i]==target){
                res++;
            }else{
                break;
            }
        }
        return res;
    }
}
